package leetcode.top100;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 滑动窗口类似见
 * {@link Code76_MinCoveredSubString_最小覆盖子串}
 * {@link Code438_字母异位词}
 * @date 2020/3/17 23:18
 */
public class Code03_LongestUnRepeatString {

    //方式1：遍历所有子序列，然后每个判断。时间复杂度是立方级别


    /**
     *
     * 方式2：滑动窗口。left始终表示窗口的起始点。
     * 用map保存已经遍历过的字符。
     * 对于位置i，字符串为c。若c已经存在，则把原来的c以及之前的位置都放弃。
     * 新的窗口起始点为left = indexof(c) + 1。
     * 更新窗口大小  i - left + 1。
     * 要注意一点：新的窗口起始点left如果之前已经被丢弃，及leftnew <= leftold，则以leftold为基准。
     * 如abba  i=2时，更新left=2. i=3，leftnew=0 < left = 2已经被淘汰了。
     */
    public static int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() <= 1) return s == null ? 0 : s.length();
        int max = 1;
        Map<Character,Integer> map = new HashMap<>();
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //得到的是离当前c最近的前面一个位置left。
            //重新从left+1位置开始计算，不包含重复
            if(map.containsKey(c)){
                //如abcdba  i=4时，left = 2，表示从index=2开始。
                // 但是i=5，map.get(a)=0已经过期了，所以至少要从left=2开始算
                left = Math.max(left,map.get(c) + 1);
            }
            max = Math.max(max,i - left + 1);// charAt(i) == charAt(left)
            //更新最新的c位置
            map.put(c,i);

        }
        return max;
    }

    public static void main(String[] args) {
        String s = "abba";
        String s1 = "bbbb";
        System.out.println(lengthOfLongestSubstring(s));
        System.out.println(lengthOfLongestSubstring(s1));
    }
}
